import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/1 15:50
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2,-3,-1,5,-4};
        System.out.println(solution.largestSumAfterKNegations(nums, 2));
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0, min = 100;
        for (int i = 0; i < n; i++) {
            // 贪心，每次取反最大值
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
            if (nums[i] < min) {
                // 记录最小的值
                min = nums[i];
            }
            ans += nums[i];
        }
        return ans - (k % 2 == 0 ? 0 : 2 * min);
    }
}
